package Algorithm.Dp;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
//https://leetcode-cn.com/problems/russian-doll-envelopes/
public class Leetcode354 {
    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            List<int[]> list = Arrays.asList(envelopes);
            Collections.sort(list, new Comparator<int[]>() {
                // @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0]-o2[0]==0?o1[1]-o2[1]:o1[0]-o2[0];
                }
            });

            int[] dp = new int[envelopes.length];
            int max = 1;
            // dp[0] = 1;
            for(int i=0;i<envelopes.length;i++){
                dp[i] = 1;
                for(int j=0;j<i;j++){
                    if(list.get(i)[0]>list.get(j)[0]&&list.get(i)[1]>list.get(j)[1]){
                        if(dp[i]<dp[j] + 1){
                            dp[i] = dp[j] + 1;
                        }
                    }
                }

                if(max<dp[i]){
                    max = dp[i];
                }
            }

            return max;
        }
    }
}
